# 在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。 
# 
#  （请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。 
# 
#  返回区域的数目。 
# 
#  
# 
#  
#  
# 
#  示例 1： 
# 
#  输入：
# [
#   " /",
#   "/ "
# ]
# 输出：2
# 解释：2x2 网格如下：
#  
# 
#  示例 2： 
# 
#  输入：
# [
#   " /",
#   "  "
# ]
# 输出：1
# 解释：2x2 网格如下：
#  
# 
#  示例 3： 
# 
#  输入：
# [
#   "\\/",
#   "/\\"
# ]
# 输出：4
# 解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
# 2x2 网格如下：
#  
# 
#  示例 4： 
# 
#  输入：
# [
#   "/\\",
#   "\\/"
# ]
# 输出：5
# 解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
# 2x2 网格如下：
#  
# 
#  示例 5： 
# 
#  输入：
# [
#   "//",
#   "/ "
# ]
# 输出：3
# 解释：2x2 网格如下：
# 
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= grid.length == grid[0].length <= 30 
#  grid[i][j] 是 '/'、'\'、或 ' '。 
#  
#  Related Topics 深度优先搜索 并查集 图 
#  👍 84 👎 0


# leetcode submit region begin(Prohibit modification and deletion)


class Solution(object):
    def regionsBySlashes(self, grid):

        # 标记节点，利用孤岛问题的解法
        """
        :type grid: List[str]
        :rtype: int
        """
        rows = len(grid)
        cols = len(grid[0])

        # 一个格子用 4*4 的格子代替 ，不能简单的用 2*2 或者 3*3   的格子替代

        board = [[0 for _ in range(0, cols * 3 + 1)] for _ in range(0, rows * 3 + 1)]

        for i in range(0, rows):
            for j in range(0, cols):

                if grid[i][j] == '/':
                    board[3 * i][j * 3 + 3], \
                    board[3 * i + 1][j * 3 + 2], \
                    board[3 * i + 2][j * 3 + 1], \
                    board[3 * i + 3][j * 3] \
                        = 1, 1, 1, 1

                elif grid[i][j] == '\\':
                    board[3 * i][j * 3], \
                    board[3 * i + 1][j * 3 + 1], \
                    board[3 * i + 2][j * 3 + 2], \
                    board[3 * i + 3][j * 3 + 3] \
                        = 1, 1, 1, 1

                    # 默认是 0 ，不用赋值处理，同时避免覆盖之前的 1

        res = 0

        for r in board:
            print(r)

        for i in range(0, rows * 3 + 1):
            for j in range(0, cols * 3 + 1):
                if board[i][j] == 0:
                    r = self.dfs(board, i, j)
                    res += r
                    if r:
                        print(i, j)
                        for r in board:
                            print(r)

        return res

    # 深度遍历
    def dfs(self, board, row, col):

        rows = len(board)
        cols = len(board[0])

        if row >= rows or col >= cols or row < 0 or col < 0 or board[row][col] != 0:
            return 0

        # 访问过的变成2
        board[row][col] = 2
        self.dfs(board, row + 1, col)
        self.dfs(board, row - 1, col)
        self.dfs(board, row, col + 1)
        self.dfs(board, row, col - 1)

        return 1


#         四个方向搜索

# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    print(Solution().regionsBySlashes(["/\\", "\\/"]))
